package com.ming.learn.from.carl.stack.and.queue;

import java.util.LinkedList;
import java.util.Queue;

/*
225. 用队列实现栈
 */
public class Of20210101LeetCode225 {
    /*
    使用队列实现栈的下列操作：
    push(x) -- 元素 x 入栈
    pop() -- 移除栈顶元素
    top() -- 获取栈顶元素
    empty() -- 返回栈是否为空
     */
    public static void main(String[] args) {
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());//3
        System.out.println(stack.top());//2
        System.out.println(stack.pop());//2
        System.out.println(stack.empty());//f
        System.out.println(stack.pop());//1
        System.out.println(stack.empty());//t
    }

}

/*
思路：
把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
 */
class MyStack {
    Queue<Integer> que1 = new LinkedList<>();
    Queue<Integer> que2 = new LinkedList<>(); // 辅助队列，用来备份

    void push(int x) {
        que1.add(x);
    }

    int pop() {
        int len = 0;
        while (!que1.isEmpty()) {
            que2.add(que1.remove());
            len++;
        }
        while (len > 1) {
            que1.add(que2.remove());
            len--;
        }
        return que2.remove();
    }

    int top() {
        int len = 0;
        while (!que1.isEmpty()) {
            que2.add(que1.remove());
            len++;
        }
        while (len > 1) {
            que1.add(que2.remove());
            len--;
        }
        int last = que2.remove();
        que1.add(last);
        return last;
    }

    boolean empty() {
        return que1.isEmpty();
    }
}